package LinkedListPackage;

/**
 * @author Lzm
 * @version 1.0
 */

/*判断链表是否有环, 有环的话找出环的入口
* 难点在于如果有环的话, 怎么找到环的入口
* 定义一个fast和slow指针, 令fast一次跳两格, slow一次跳一格
* 当fast == slow时, 说明此链表有环
*
* 当fast和slow相遇时, 相遇到环的入口, 且移动的时间相同
* fast走了 x + y + n(y + z)
* slow走了 x + y
* 根据相遇时fast和slow走了相同的时间 而fast速度为2, slow速度为1
* 故 [x + y + n(y + z)] / 2 = [x + y] / 1
* 有 n(y + z) = x + y
* 假如n = 1, 有z = x
* 假如n为任意正整数 则 x = (n - 1)(z + y) + z
* 这里可以看出 当slow 走到环的入口的距离和fast走到环的入口距离一致
* 即 x = z
* */
public class detectCycle_ {

  public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null){
      return null;
    }
    ListNode dummyHead = new ListNode();
    dummyHead.next = head;
    ListNode slow = dummyHead;
    ListNode fast = dummyHead;
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if (fast == slow){
          ListNode temp1 = dummyHead.next;
          ListNode temp2 = fast;
          while(true){
            if (temp1 == temp2){
              return temp1;
            }
            temp1 = temp1.next;
            temp2 = temp2.next;
          }
        }
    }
    return null;
  }
}
